package demo10;

public class BinarySearchForRotatingArray {
    public BinarySearch createBinarySearch(){
        return new BinarySearch();
    }
    public class BinarySearch{
        /**
         *
         */
        public int binarySearch(int[] arr, int val){
            return binarySearchPos(arr,val,0,arr.length-1);
        }
        public int binarySearchForVal(int[] arr, int val){
            return binarySearchVal(arr,val,0,arr.length-1);
        }

        public int binarySearchVal(int[] arr,int val,int low ,int high){
            if(low<=high) {
                int middle = (low + high) / 2;
                if(arr[middle]>val){ // left
                    return binarySearchVal(arr, val,low,middle-1 );
                }else if (arr[middle]<val){
                    return binarySearchVal(arr,val,middle+1,high  );
                }else{
                    return middle;
                }
            }
            return -1;
        }
        //  the Time: O(logn) when ele unique , else O(n)
//        int[] intA = {15, 16, 19, 20, 25, 1, 3, 4, 5, 7, 10, 14}; find the val = 7
        // int[] intA = {15, 16, 19, 20, 25, 1,3, 4, 5, 7, 10, 14}; find the val = 20
        //
        public int binarySearchPos(int[] arr ,int val, int low,int high){
            if(low<=high) {
                int middle = (low + high) / 2;
                if(arr[middle]==val){
                    return middle;
                }
                //  @importance  the judge condition need is mutually exclusive
                if (arr[low]>arr[middle] ) {
                        if (arr[middle]>val){  // find the right
                            return binarySearchPos(arr, val, low, middle - 1);
                        }else if(arr[middle]<val){// find the left
                            return binarySearchPos(arr, val, middle + 1, high);
                        }else{
                            return low;
                        }
                        // 14, 15 , 16 ,19, 20, 25, 1,3, 4,  5, 7, 10, find the 7
                        // 14, 15 , 16 ,19, 20, 25, 1,3, 4,  5, 7, 10, find the 16
                } else if (arr[low]< arr[middle] ) {
                    if(arr[middle]>val){
                        return binarySearchPos(arr, val, low, middle - 1);
                    }else if(arr[middle]<val){
                        return binarySearchPos(arr, val, middle + 1, high);
                    }else{
                        return high;
                    }
                } else if (arr[low]==arr[middle]){ // if find the dup ele , then left and right need search
                    if(arr[middle]!=arr[high]){  // {2,2,2,3,4,5};  find the Number 5
                        return binarySearchPos(arr, val, middle + 1, high); // find the right
                    }else { // {2,2,2,3,2};
                            // {2,3,2,2,2};
                         // find the left and right

                        int i = binarySearchPos(arr, val, low, middle - 1);
                        if(i!=-1){
                            return i;
                        }
                        i = binarySearchPos(arr, val, middle + 1, high);
                        if(i!=-1){
                            return i;
                        }

                    }

                }
            }
            return -1;
        }

    }
}
